package org.gzc.stack.calculate;

import java.util.*;

/**
 * @Description:
 * @Author: guozongchao
 * @Date: 2020/8/5 20:43
 */
public class SuffixExpressionCalculateStrategy implements CalculateStrategy {

    @Override
    public double calculate(String expression) {
        Stack<String> stack = new Stack<>();
        //将中缀表达式转换为后缀表达式，返回切分后列表
        List<String> expList = transferToSuffixExpressionList(splitExpression(expression));
        for (String s: expList) {
            if (isNumberOrPoint(s)) {  //如果是操作数，直接入栈
                stack.push(s);
            }else {   //如果是操作符，则弹出两个操作数进行运算，再将结果压入栈
                String num1 = stack.pop();
                String num2 = stack.pop();
                double result = calculate(Double.valueOf(num1), Double.valueOf(num2), s);
                stack.push(String.valueOf(result));
            }
        }
        return Double.valueOf(stack.pop());
    }


    //切分表达式，将操作符和数字分别按原来顺序存放在list中
    private List<String> splitExpression(String exp) {
        String expression = exp.replace(" ", "");
        int index = 0;
        String num = "";
        List<String> list = new ArrayList<>();

        while (index != expression.length()) {
            String c = expression.substring(index, index + 1);
            //如果是操作数,拼接多位操作数
            if (isNumberOrPoint(c)) {
                num += c;
                //如果下一个字符是操作符，则将当前的num加入到list中
                if (index == expression.length() - 1 || isOperator(expression.substring(index + 1, index + 2))) {
                    list.add(num);
                    num = "";
                }
            }
            //否则为操作符，直接加入到list中
            if (isOperator(c)) {
                list.add(c);
            }

            index++;
        }
        return list;
    }

    //判断是否为操作符
    private boolean isOperator(String operator) {
        //正则匹配* / - + ( )符号
        return operator.matches("[\\*\\/\\+\\-\\(\\)]");
    }

    //判断是否为操作数或小数点
    private boolean isNumberOrPoint(String operator) {
        //正则匹配数字或"."符号
        return operator.matches("(\\d+)|(\\.)|(\\d+.\\d+)");
    }

    //返回操作符的优先级
    private int priority(String operator) {
        switch (operator) {
            case "+":
            case "-":
                return 0;
            case "*":
            case "/":
                return 1;
            default:
                return -1;
        }
    }

    //计算
    private double calculate(double num1, double num2, String op) {
        switch (op) {
            case "+":
                return num2 + num1;
            case "-":
                return num2 - num1;
            case "*":
                return num2 * num1;
            case "/":
                return num2 / num1;
            default:
                throw new RuntimeException("暂不支持该操作符[" + op + "]运算");
        }
    }

    /**
     * 将中缀表达式转换为后缀表达式，返回切分后的列表
     * @param expList
     * @return
     */
    private List<String> transferToSuffixExpressionList(List<String> expList) {
        Stack<String> resultStack = new Stack<>();  //存放最终转换后的结果栈
        Stack<String> tempStack = new Stack<>();   //存放操作符的临时栈
        for (String s : expList) {
            if (isNumberOrPoint(s)) {   //如果是操作数，直接入结果栈
                resultStack.push(s);
            }
            else if(isOperator(s)) {  //如果是操作符
                if (tempStack.isEmpty()||"(".equals(s)) {   //如果临时操作符栈为空，或者当前符号为"("，则直接入栈
                    tempStack.push(s);
                } else if ( priority(s) > priority((String) tempStack.peek())) {  //如果当前操作符优先级大于栈顶符号,入栈
                    tempStack.push(s);
                }else if(")".equals(s)){  //如果是")",则从临时符号栈中弹出符号，并压入结果栈中，知道遇到"("结束
                    String op = tempStack.pop();
                    while (!"(".equals(op)) {
                        resultStack.push(op);
                        op = tempStack.pop();
                    }
                }else {   //否则，就弹出优先级高的栈顶符号，并压入结果栈
                    resultStack.push(tempStack.pop());
                    tempStack.push(s);
                }
            }
            else {
                throw new RuntimeException("表达式错误");
            }
        }
        //检查临时操作符栈是否还有元素
        while (!tempStack.isEmpty()) {
            resultStack.push(tempStack.pop());
        }

        //逆序取出结果栈的元素,这里再次利用前面已将为空的tempStack
        while (!resultStack.isEmpty()) {
            tempStack.push(resultStack.pop());
        }
        List<String> result = new ArrayList<>();
        while (!tempStack.isEmpty()) {
            result.add(tempStack.pop());
        }
        return result;
    }

    public static void main(String[] args) {
        SuffixExpressionCalculateStrategy secs = new SuffixExpressionCalculateStrategy();
       // "1 2 3 + 4 × + 5 –
        List<String> list1 = secs.splitExpression("1+((2+3)*4)-5");
        List<String> list2 = secs.transferToSuffixExpressionList(list1);
        System.out.println(list1);
        System.out.println(list2);
    }

}
